#include<iostream>
#include<sys/time.h>
using namespace std;

const static int SIZ = 2048;
double Res[3] = { 0 };
double idata[SIZ] = { 0 };
double buf[SIZ] = { 0 };

double simpleAdd(double* a, int size);
double normalAdd(double* a, int size);
double assignAdd(double* a, int size);
double assiproAdd(double* a, int size);

int main()
{
	struct timeval sign1, sign2, sign3, sign4, sign5;
	for (int i = 0; i < SIZ; i += 1)
	{
		idata[i] = 1.5 * i;
	}
	for (int i = 0; i < SIZ; i += 1)
	{
		printf("%lf ", idata[i]);
	}
	
	gettimeofday(&sign1, NULL);
	for (int o = 0; o < 1000; o += 1)
	{
		Res[0] = simpleAdd(idata, SIZ);//简单求和（for循环）
	}
	gettimeofday(&sign2, NULL);
	for (int o = 0; o < 1000; o += 1)
	{
		Res[1] = normalAdd(idata, SIZ);//平凡求和（递归）
	}
	gettimeofday(&sign3, NULL);
	for (int o = 0; o < 1000; o += 1)
	{
		Res[2] = assignAdd(idata, SIZ);//告急求和（分配）
	}
	gettimeofday(&sign4, NULL);
	for (int o = 0; o < 1000; o += 1)
	{
		Res[3] = assiproAdd(idata, SIZ);//减递归求和
	}
	gettimeofday(&sign5, NULL);

	for (int i = 0; i < 3; i += 1)
	{
		printf("\n第%d种求和算法结果：%lf\n", i, Res[i]);
	}
	cout << "简单算法时间/us: "
		<< (sign2.tv_sec*1000*1000+sign2.tv_usec)
			-(sign1.tv_sec*1000*1000+sign1.tv_usec);
	cout << "\n平凡算法时间/us: "
		<< (sign3.tv_sec*1000*1000+sign3.tv_usec)
			-(sign2.tv_sec*1000*1000+sign2.tv_usec);
	cout << "\n告急算法时间/us: "
		<< (sign4.tv_sec*1000*1000+sign4.tv_usec)
			-(sign3.tv_sec*1000*1000+sign3.tv_usec);
	cout << "\n减递归算法时间/us: "
		<< (sign5.tv_sec*1000*1000+sign5.tv_usec)
			-(sign4.tv_sec*1000*1000+sign4.tv_usec)<<'\n';

	return 0;
}


double simpleAdd(double* a, int size)
{
	double rt = 0.0;
	for (int i = 0; i < size; i += 1)
	{
		rt += a[i];
	}
	return rt;
}
double normalAdd(double* a, int size)
{
	if (size == 1)
		return a[0];
	return normalAdd(a, size - 1) + a[size - 1];
}
double assignAdd(double* a, int size)
{
	switch (size)
	{
	case 1:
		return a[0];
	case 2:
		return a[0] + a[1];
	default:
		return assignAdd(a, size / 2) + assignAdd(&a[size / 2], size - size / 2);
	}
}
double assiproAdd(double* a, int size)
{
	if (size == 1)
		return *a;
	for (int i = 0; i < size / 2; i += 1)
	{
		buf[i] = a[i] + a[size - 1 - i];
	}
	return assiproAdd(buf, size - size / 2);
}

